home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 1994 November: Tool Chest / Dev.CD Nov 94.toast / Tool Chest / Development Tools & Languages / • Other Platforms / PCCTS / support / sym / sym.c next >
Encoding:
C/C++ Source or Header  |  1994-09-14  |  8.9 KB  |  367 lines  |  [TEXT/MPS ]
  1. /*
  2.  * Simple symbol table manager using coalesced chaining to resolve collisions
  3.  *
  4.  * Doubly-linked lists are used for fast removal of entries.
  5.  *
  6.  * 'sym.h' must have a definition for typedef "Sym".  Sym must include at
  7.  * minimum the following fields:
  8.  *
  9.  *        ...
  10.  *        char *symbol;
  11.  *        struct ... *next, *prev, **head, *scope;
  12.  *        unsigned int hash;
  13.  *        ...
  14.  *
  15.  * 'template.h' can be used as a template to create a 'sym.h'.
  16.  *
  17.  * 'head' is &(table[hash(itself)]).
  18.  * The hash table is not resizable at run-time.
  19.  * The scope field is used to link all symbols of a current scope together.
  20.  * Scope() sets the current scope (linked list) to add symbols to.
  21.  * Any number of scopes can be handled.  The user passes the address of
  22.  * a pointer to a symbol table
  23.  * entry (INITIALIZED TO NULL first time).
  24.  *
  25.  * Available Functions:
  26.  *
  27.  *    zzs_init(s1,s2)    --    Create hash table with size s1, string table size s2.
  28.  *    zzs_done()        --    Free hash and string table created with zzs_init().
  29.  *    zzs_add(key,rec)--    Add 'rec' with key 'key' to the symbol table.
  30.  *    zzs_newadd(key)    --    create entry; add using 'key' to the symbol table.
  31.  *    zzs_get(key)    --    Return pointer to last record entered under 'key'
  32.  *                        Else return NULL
  33.  *    zzs_del(p)        --    Unlink the entry associated with p.  This does
  34.  *                        NOT free 'p' and DOES NOT remove it from a scope
  35.  *                        list.  If it was a part of your intermediate code
  36.  *                        tree or another structure.  It will still be there.
  37.  *                          It is only removed from further consideration
  38.  *                        by the symbol table.
  39.  *    zzs_keydel(s)    --    Unlink the entry associated with key s.
  40.  *                        Calls zzs_del(p) to unlink.
  41.  *    zzs_scope(sc)    --    Specifies that everything added to the symbol
  42.  *                           table with zzs_add() is added to the list (scope)
  43.  *                        'sc'.  'sc' is of 'Sym **sc' type and must be
  44.  *                        initialized to NULL before trying to add anything
  45.  *                        to it (passing it to zzs_scope()).  Scopes can be
  46.  *                        switched at any time and merely links a set of
  47.  *                        symbol table entries.  If a NULL pointer is
  48.  *                        passed, the current scope is returned.
  49.  *    zzs_rmscope(sc)    --    Remove (zzs_del()) all elements of scope 'sc'
  50.  *                        from the symbol table.  The entries are NOT
  51.  *                        free()'d.  A pointer to the first
  52.  *                           element in the "scope" is returned.  The user
  53.  *                           can then manipulate the list as he/she chooses
  54.  *                           (such as freeing them all). NOTE that this
  55.  *                           function sets your scope pointer to NULL,
  56.  *                           but returns a pointer to the list for you to use.
  57.  *    zzs_stat()        --    Print out the symbol table and some relevant stats.
  58.  *    zzs_new(key)    --    Create a new record with calloc() of type Sym.
  59.  *                           Add 'key' to the string table and make the new
  60.  *                           records 'symbol' pointer point to it.
  61.  *    zzs_strdup(s)    --    Add s to the string table and return a pointer
  62.  *                           to it.  Very fast allocation routine
  63.  *                        and does not require strlen() nor calloc().
  64.  *
  65.  * Example:
  66.  *
  67.  *    #include <stdio.h>
  68.  *    #include "sym.h"
  69.  *
  70.  *    main()
  71.  *    {
  72.  *        Sym *scope1=NULL, *scope2=NULL, *a, *p;
  73.  *    
  74.  *        zzs_init(101, 100);
  75.  *    
  76.  *        a = zzs_new("Apple");    zzs_add(a->symbol, a);    -- No scope
  77.  *        zzs_scope( &scope1 );    -- enter scope 1
  78.  *        a = zzs_new("Plum");    zzs_add(a->symbol, a);
  79.  *        zzs_scope( &scope2 );    -- enter scope 2
  80.  *        a = zzs_new("Truck");    zzs_add(a->symbol, a);
  81.  *    
  82.  *        p = zzs_get("Plum");
  83.  *        if ( p == NULL ) fprintf(stderr, "Hmmm...Can't find 'Plum'\n");
  84.  *    
  85.  *        p = zzs_rmscope(&scope1)
  86.  *        for (; p!=NULL; p=p->scope) {printf("Scope1:  %s\n", p->symbol);}
  87.  *        p = zzs_rmscope(&scope2)
  88.  *        for (; p!=NULL; p=p->scope) {printf("Scope2:  %s\n", p->symbol);}
  89.  * }
  90.  *
  91.  * Terence Parr
  92.  * Purdue University
  93.  * February 1990
  94.  *
  95.  * CHANGES
  96.  *
  97.  *    Terence Parr
  98.  *    May 1991
  99.  *        Renamed functions to be consistent with ANTLR
  100.  *        Made HASH macro
  101.  *        Added zzs_keydel()
  102.  *        Added zzs_newadd()
  103.  *        Fixed up zzs_stat()
  104.  *
  105.  *    July 1991
  106.  *        Made symbol table entry save its hash code for fast comparison
  107.  *            during searching etc...
  108.  */
  109.  
  110. #include <stdio.h>
  111. #if __STDC__ == 1
  112. #include <string.h>
  113. #include <stdlib.h>
  114. #else
  115. #include "malloc.h"
  116. #endif
  117. #ifdef MEMCHK
  118. #include "trax.h"
  119. #endif
  120. #include "sym.h"
  121.  
  122. #define StrSame        0
  123.  
  124. static Sym **CurScope = NULL;
  125. static unsigned size = 0;
  126. static Sym **table=NULL;
  127. static char *strings;
  128. static char *strp;
  129. static int strsize = 0;
  130.  
  131. void
  132. zzs_init(sz, strs)
  133. int sz, strs;
  134. {
  135.     if ( sz <= 0 || strs <= 0 ) return;
  136.     table = (Sym **) calloc(sz, sizeof(Sym *));
  137.     if ( table == NULL )
  138.     {
  139.         fprintf(stderr, "Cannot allocate table of size %d\n", sz);
  140.         exit(1);
  141.     }
  142.     strings = (char *) calloc(strs, sizeof(char));
  143.     if ( strings == NULL )
  144.     {
  145.         fprintf(stderr, "Cannot allocate string table of size %d\n", strs);
  146.         exit(1);
  147.     }
  148.     size = sz;
  149.     strsize = strs;
  150.     strp = strings;
  151. }
  152.  
  153. void
  154. zzs_done()
  155. {
  156.     if ( table != NULL ) free( table );
  157.     if ( strings != NULL ) free( strings );
  158. }
  159.  
  160. void
  161. zzs_add(key, rec)
  162. char *key;
  163. register Sym *rec;
  164. {
  165.     register unsigned int h=0;
  166.     register char *p=key;
  167.     extern Sym *Globals;
  168.     
  169.     HASH(p, h);
  170.     rec->hash = h;                    /* save hash code for fast comp later */
  171.     h %= size;
  172.     
  173.     if ( CurScope != NULL ) {rec->scope = *CurScope; *CurScope = rec;}
  174.     rec->next = table[h];            /* Add to doubly-linked list */
  175.     rec->prev = NULL;
  176.     if ( rec->next != NULL ) (rec->next)->prev = rec;
  177.     table[h] = rec;
  178.     rec->head = &(table[h]);
  179. }
  180.  
  181. Sym *
  182. zzs_get(key)
  183. char *key;
  184. {
  185.     register unsigned int h=0;
  186.     register char *p=key;
  187.     register Sym *q;
  188.     
  189.     HASH(p, h);
  190.     
  191.     for (q = table[h%size]; q != NULL; q = q->next)
  192.     {
  193.         if ( q->hash == h )        /* do we even have a chance of matching? */
  194.             if ( strcmp(key, q->symbol) == StrSame ) return( q );
  195.     }
  196.     return( NULL );
  197. }
  198.  
  199. /*
  200.  * Unlink p from the symbol table.  Hopefully, it's actually in the
  201.  * symbol table.
  202.  *
  203.  * If p is not part of a bucket chain of the symbol table, bad things
  204.  * will happen.
  205.  *
  206.  * Will do nothing if all list pointers are NULL
  207.  */
  208. void
  209. zzs_del(p)
  210. register Sym *p;
  211. {
  212.     if ( p == NULL ) {fprintf(stderr, "zzs_del(NULL)\n"); exit(1);}
  213.     if ( p->prev == NULL )    /* Head of list */
  214.     {
  215.         register Sym **t = p->head;
  216.         
  217.         if ( t == NULL ) return;    /* not part of symbol table */
  218.         (*t) = p->next;
  219.         if ( (*t) != NULL ) (*t)->prev = NULL;
  220.     }
  221.     else
  222.     {
  223.         (p->prev)->next = p->next;
  224.         if ( p->next != NULL ) (p->next)->prev = p->prev;
  225.     }
  226.     p->next = p->prev = NULL;    /* not part of symbol table anymore */
  227.     p->head = NULL;
  228. }
  229.  
  230. void
  231. zzs_keydel(key)
  232. char *key;
  233. {
  234.     Sym *p = zzs_get(key);
  235.  
  236.     if ( p != NULL ) zzs_del( p );
  237. }
  238.  
  239. /* S c o p e  S t u f f */
  240.  
  241. /* Set current scope to 'scope'; return current scope if 'scope' == NULL */
  242. Sym **
  243. zzs_scope(scope)
  244. Sym **scope;
  245. {
  246.     if ( scope == NULL ) return( CurScope );
  247.     CurScope = scope;
  248.     return( scope );
  249. }
  250.  
  251. /* Remove a scope described by 'scope'.  Return pointer to 1st element in scope */
  252. Sym *
  253. zzs_rmscope(scope)
  254. register Sym **scope;
  255. {
  256.     register Sym *p;
  257.     Sym *start;
  258.  
  259.     if ( scope == NULL ) return(NULL);
  260.     start = p = *scope;
  261.     for (; p != NULL; p=p->scope) { zzs_del( p ); }
  262.     *scope = NULL;
  263.     return( start );
  264. }
  265.  
  266. void
  267. zzs_stat()
  268. {
  269.     static unsigned short count[20];
  270.     unsigned int i,n=0,low=0, hi=0;
  271.     register Sym **p;
  272.     float avg=0.0;
  273.     
  274.     for (i=0; i<20; i++) count[i] = 0;
  275.     for (p=table; p<&(table[size]); p++)
  276.     {
  277.         register Sym *q = *p;
  278.         unsigned int len;
  279.         
  280.         if ( q != NULL && low==0 ) low = p-table;
  281.         len = 0;
  282.         if ( q != NULL ) printf("[%d]", p-table);
  283.         while ( q != NULL )
  284.         {
  285.             len++;
  286.             n++;
  287.             printf(" %s", q->symbol);
  288.             q = q->next;
  289.             if ( q == NULL ) printf("\n");
  290.         }
  291.         if ( len>=20 ) printf("zzs_stat: count table too small\n");
  292.         else count[len]++;
  293.         if ( *p != NULL ) hi = p-table;
  294.     }
  295.  
  296.     printf("Storing %d recs used %d hash positions out of %d\n",
  297.             n, size-count[0], size);
  298.     printf("%f %% utilization\n",
  299.             ((float)(size-count[0]))/((float)size));
  300.     for (i=0; i<20; i++)
  301.     {
  302.         if ( count[i] != 0 )
  303.         {
  304.             avg += (((float)(i*count[i]))/((float)n)) * i;
  305.             printf("Buckets of len %d == %d (%f %% of recs)\n",
  306.                     i, count[i], 100.0*((float)(i*count[i]))/((float)n));
  307.         }
  308.     }
  309.     printf("Avg bucket length %f\n", avg);
  310.     printf("Range of hash function: %d..%d\n", low, hi);
  311. }
  312.  
  313. /*
  314.  * Given a string, this function allocates and returns a pointer to a
  315.  * symbol table record whose "symbol" pointer is reset to a position
  316.  * in the string table.
  317.  */
  318. Sym *
  319. zzs_new(text)
  320. char *text;
  321. {
  322.     Sym *p;
  323.     char *zzs_strdup();
  324.     
  325.     if ( (p = (Sym *) calloc(1,sizeof(Sym))) == 0 )
  326.     {
  327.         fprintf(stderr,"Out of memory\n");
  328.         exit(1);
  329.     }
  330.     p->symbol = zzs_strdup(text);
  331.     
  332.     return p;
  333. }
  334.  
  335. /* create a new symbol table entry and add it to the symbol table */
  336. Sym *
  337. zzs_newadd(text)
  338. char *text;
  339. {
  340.     Sym *p = zzs_new(text);
  341.     if ( p != NULL ) zzs_add(text, p);
  342.     return p;
  343. }
  344.  
  345. /* Add a string to the string table and return a pointer to it.
  346.  * Bump the pointer into the string table to next avail position.
  347.  */
  348. char *
  349. zzs_strdup(s)
  350. register char *s;
  351. {
  352.     register char *start=strp;
  353.  
  354.     while ( *s != '\0' )
  355.     {
  356.         if ( strp >= &(strings[strsize-2]) )
  357.         {
  358.             fprintf(stderr, "sym: string table overflow (%d chars)\n", strsize);
  359.             exit(-1);
  360.         }
  361.         *strp++ = *s++;
  362.     }
  363.     *strp++ = '\0';
  364.  
  365.     return( start );
  366. }
  367.